P6271 [湖北省队互测2014]一个人的数论

注意本篇题解的 $k$ 是题目中的 $d$。

$\sum_{i=1}^n[\gcd(i,n)=1]i^k$

$\sum_{i=1}^ni^k\sum_{d|\gcd(i,n)}\mu(d)$

$\sum_{d|n}\mu(d)d^k\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}i^k$

$\sum_{d|n}\mu(d)d^k(S_k(\frac{n}{d})+(\frac{n}{d})^k)$

$\sum_{d|n}\mu(d)d^kS_k(\frac{n}{d})+\sum_{d|n} \mu(d)d^k(\frac{n}{d})^k$

$\sum_{d|n}\mu(d)d^kS_k(\frac{n}{d})+n^k\sum_{d|n} \mu(d)$

$\sum_{d|n}\mu(d)d^kS_k(\frac{n}{d})+n^k[n=1]$

这道题 $n$ 肯定不为 $1$ , 后面的值为 $0$，只需考虑前一个和式。

自然数幂和是一个 $k+1$ 次多项式，可以用伯努利数算出系数，不妨记为 $f_i$。

由伯努利公式得：$f_{k+1-i}=\frac{\binom{k+1}{i}B_i}{k+1}$

$\sum_{d|n}\mu(d)d^k \sum_{i=1}^{k+1} f_i \left ( \frac{n}{d} \right)^{i}$

$\sum_{i=1}^{k+1} f_i\sum_{d|n}\mu(d)d^k \left( \frac{n}{d} \right)^{i}$

$\sum_{i=1}^{k+1} f_i n^i\sum_{d|n}\mu(d) d^{k-i}$

后面的和式是一个积性函数，考虑质数取值

$\sum_{d|p^w}\mu(d)d^{k-i}$

$\sum_{i=0}^w \mu(p^i)p^{i(k-i)}$

由 $\mu$ 的性质，只有 $i=0$ 或 $1$ 时不为 $0$，所以上式等于 $1-p^{k-i}$。

所以我们能 $\mathcal O(w)$ 计算出这个式子。

那么预处理出伯努利数和 $f$ ，原题便能 $\mathcal O(d^2+dw)$ 解决了。

#include <cstdio>

const int MAXK = 105 , Mod = 1e9 + 7;

int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int Quick_pow( int x , int po ) { int Ans = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) Ans = Mul( Ans , x ); return Ans; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return Mul( x , Inv( y ) ); }

int fac[ MAXK + 10 ] , ivf[ MAXK + 10 ];
void Init( ) {
    fac[ 0 ] = 1;
    for( int i = 1 ; i <= MAXK + 5 ; i ++ ) fac[ i ] = Mul( fac[ i - 1 ] , i );
    ivf[ MAXK + 5 ] = Inv( fac[ MAXK + 5 ] );
    for( int i = MAXK + 5 ; i >= 1 ; i -- ) ivf[ i - 1 ] = Mul( ivf[ i ] , i );
}
int C( int n , int m ) { return Mul( fac[ n ] , Mul( ivf[ m ] , ivf[ n - m ] ) ); }

int w , k , p[ 1005 ] , a[ 1005 ];

int B[ MAXK + 5 ] , f[ MAXK + 5 ];
void Init_Bernoulli( ) {
    B[ 0 ] = 1;
    for( int i = 1 ; i <= MAXK ; i ++ ) {
        int Sum = 0;
        for( int j = 0 ; j < i ; j ++ ) Sum = Add( Sum , Mul( C( i + 1 , j ) , B[ j ] ) );
        B[ i ] = Sub( 0 , Mul( Sum , Inv( C( i + 1 , i ) ) ) );
    }
    for( int i = 0 ; i <= k ; i ++ ) f[ k + 1 - i ] = Div( Mul( C( k + 1 , i ) , B[ i ] ) , k + 1 );
}

int Sum( int pw ) {
    if( pw < 0 ) pw += Mod - 1;
    int Ans = 1;
    for( int i = 1 ; i <= w ; i ++ ) Ans = Mul( Ans , Sub( 1 , Quick_pow( p[ i ] , pw ) ) );
    return Ans;
}

int main( ) {
    scanf("%d %d",&k,&w);
    Init(); Init_Bernoulli();
    for( int i = 1 ; i <= w ; i ++ ) scanf("%d %d",&p[ i ],&a[ i ]);

    int Ans = 0 , n = 1;
    for( int i = 1 ; i <= w ; i ++ ) n = Mul( n , Quick_pow( p[ i ] , a[ i ] ) );
    for( int i = 1 , nk = 1 ; i <= k + 1 ; i ++ ) {
        nk = Mul( nk , n );
        Ans = Add( Ans , Mul( Mul( f[ i ] , nk ) , Sum( k - i ) ) );
    }
    printf("%d\n", Ans );
    return 0;
}